import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class Solution84 {
    public int largestRectangleArea(int[] heights) {
        Deque<int[]> stack = new LinkedList<>(); // 0 : loc ; 1 : height ;
        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            int tmpHeight = heights[i];
            int startInd = i;
            while(!stack.isEmpty()){
                int[] peekInfo = stack.peekLast();
                if(peekInfo[1] > tmpHeight){
                    res = Math.max(res, (i - peekInfo[0]) * peekInfo[1]);
                    startInd = peekInfo[0];
                    stack.pollLast();
                }
                else{ break; }
            }
            stack.add(new int[]{startInd, tmpHeight});
        }
        while(!stack.isEmpty()){
            int[] peekInfo = stack.pollLast();
            res = Math.max(res, (heights.length - peekInfo[0]) * peekInfo[1]);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution84 s = new Solution84();
        s.largestRectangleArea(
                new int[]{4,2,0,3,2,4,3,4});
    }
}
